/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package Controller;

import Exceptions.ElementAlreadyExistsException;
import java.awt.Point;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 *
 * @author asouza, subx
 */
public class Graph {

    private List<Node> nodes;
    private List<List<Edge>> matrix;


    /**
     * Construtor vazio.
     */
    public Graph() {
        nodes = new LinkedList<Node>();
        matrix = new LinkedList();
    }

    /**
     * Checa se o grafo está vazio.
     * @return true se sim, false caso contrario.
     */

    public boolean isEmpty(){
        return (getNodes().isEmpty() && getMatrix().isEmpty());
    }

    /**
     * Retorna a lista dos vertices do grafo.
     * @return - lista dos vertices
     */

    public List<Node> getNodes() {
        if(nodes == null)
            nodes = new LinkedList<Node>();
        
        return nodes;
    }

    /**
     * Retorna um nó a partir de seu indice.
     * @param index - indice
     * @return no encontrado
     */

    public Node getNode(int index) {
        return getNodes().get(index);
    }

    /**
     * Seta uma nova lista de nós para o grafo.
     * @param nodes - a nova lista
     */

    public void setNodes(List<Node> nodes) {
        this.nodes = nodes;
    }

    /**
     * Retorna a lista de adjacencia do grafo.
     * @return - a lista de adjacencia
     */
    
    public List<List<Edge>> getMatrix() {
        return matrix;
    }

    /**
     * Retorna a lista de arestas a partir de um dado vertice
     * @param index - id do vertice
     * @return - lista das arestas
     */

    public List<Edge> getEdgesList(int index){
        if(getMatrix().get(index) == null)
            getMatrix().add(index, new LinkedList<Edge>());
        
        return getMatrix().get(index);
    }

    /**
     * Seta uma nova aresta para um dado vertice.
     * @param index - id do vertice
     * @param edge - nova aresta
     */

    public void setEdgesList(int index, Edge edge){
        if(getMatrix().size() <= index)
            while (getMatrix().size() <= index) {
                getMatrix().add(new LinkedList<Edge>());
            }

        getMatrix().get(index).add(edge);
    }

     /**
      * Define uma nova lista de adjacencia para o grafo.
      * @param matrix - nova lista de adjacencia
      */
    public void setMatrix(List<List<Edge>> matrix) {
        this.matrix = matrix;
    }

    /**
     * Cria novo nó e insere em nodes.
     * 
     * @param id ID do nó.
     * @param x Coordenada X no mapa.
     * @param y Coordenada Y no mapa.
     * @param weight Peso do nó.
     */
    public void setNode(int id, int x, int y, int weight){
        Node node = new Node(id, x, y, weight, this);

        getNodes().add(id, node);
    }

    /**
     * Insere uma nova aresta no grafo.
     * @param id - vertice de partida
     * @param ide - vertice de chegada
     * @param weight - peso da aresta
     */

    public void setEdge(int id, int ide, int weight){
        Edge edge = new Edge(id, ide, weight, this);
        Edge reverseEdge = new Edge(ide, id, weight, this);
        Point p = new Point(0,0);

        edge.setStart(p);
        edge.setEnd(p);
        reverseEdge.setEnd(p);
        reverseEdge.setStart(p);
        
        setEdgesList(id, edge);
        setEdgesList(ide, reverseEdge);
    }

    /**
     * Função utilizada para a copia de arestas.
     * @param id - vertice de partida
     * @param ide - vertice de chegada
     * @param weight - peso da aresta
     */

    public void copyEdge (int id, int ide, int weight) {
        Edge edge = new Edge(id, ide, weight, this);

        setEdgesList(id, edge);
    }

    /**
     * Remove uma dada aresta.
     * @param id - id do vertice de partida
     * @param ide - id do vertice de chegada
     * @return a aresta removida.
     */

    public Edge removeEdge (int id, int ide) {
        Edge aux = new Edge();
        for (int i = 0; i < getEdgesList(id).size(); i++) {
            if (getEdgesList(id).get(i).getIde() == ide) {
                aux = getEdgesList(id).remove(i);
                break;
            }
        }
        return aux;
    }

    /**
     * Atualiza todas as arestas com as posições dos nós que as constituem.
     */
    public void Update() {
        Point start, end;

        for(List<Edge> l : getMatrix()){
            for(Edge e : l){
                start = getNode(e.getId()).getPosition();
                end = getNode(e.getIde()).getPosition();

                e.setStart(start);
                e.setEnd(end);
            }
        }
    }

    /**
     * Função que checa se um grafo é euleriano, ou seja, se todos os vertices tem grau par.
     * @return true se sim, false caso contrario.
     */

    public boolean isEulerian () {
        boolean result = true;
        for (List<Edge> l : getMatrix()) {
            if (l.size() % 2 != 0) {
                result = false;
            }
        }
        return result;
    }

    /**
     * Função que checa se o grafo é conexo.
     * @return true se sim, false caso contrario.
     */

    public boolean isConnected () {
        int iterations = 0;
        LinkedList<Node> visited = new LinkedList<Node>();
        visited.add(nodes.get(0));

        while (nodes.size() != visited.size() && iterations < visited.size()) {
            for (Node it : getSucessors(visited.get(iterations).getId())) {
                Node aux = it;
                if (!visited.contains(aux))
                    visited.add(aux);
            }
            iterations++;
        }

        return (nodes.size() == visited.size());
    }

    /**
     * Função que monta uma lista contendo os nós que tem o grau ímpar.
     * @return Lista de nós com grau impar.
     */

    public LinkedList<Node> getOddDegreeNodes () {
        LinkedList<Node> oddDegree = new LinkedList<Node>();
        int i = 0;
        for (List<Edge> l : getMatrix()) {
            if (l.size() % 2 != 0) {
                oddDegree.add(this.getNode(i));
            }
            i++;
        }
        return oddDegree;
    }


    
    /**
     * Função responsável por encontrar o caminho euleriano a partir do nó 0.
     * @return Lista de arestas ordenada segundo o caminho euleriano.
     */


    public LinkedList<Edge> eulerianPath () {
        ArrayList <Node> path = new ArrayList<Node>();
        ArrayList <Node> pathAux = new ArrayList<Node>();
        LinkedList <Edge> pathEdge = new LinkedList<Edge>();
        LinkedList <Edge> pathEdgeAux = new LinkedList<Edge>();

        ArrayList <Node> exausted = new ArrayList<Node>();
        Graph graphAux = new Graph();

        for (int i = 0; i < this.getNodes().size(); i++) {
            graphAux.setNode(getNodes().get(i).getId(), (int)getNodes().get(i).getPosition().getX(),
                                (int)getNodes().get(i).getPosition().getY(), getNodes().get(i).getWeight());
        }

        for(List<Edge> l : getMatrix()){
            for(Edge e : l){
                graphAux.copyEdge(e.getId(), e.getIde(), e.getWeight());
            }
        }

        
        Node current = graphAux.getNode(0);
        int x = 0;
        path.add(current);

        while (true) {
            if (graphAux.getSucessors(current.getId()).size() != 0) {
                pathAux.add(current);
                Node aux = graphAux.getSucessors(current.getId()).get(0);
                pathEdgeAux.add(graphAux.removeEdge(current.getId(), aux.getId()));
                if (graphAux.getSucessors(current.getId()).size() == 0) {
                    exausted.add(current);
                }
                graphAux.removeEdge(aux.getId(), current.getId());
                if (graphAux.getSucessors(aux.getId()).size() == 0) {
                    exausted.add(aux);
                }
                current = aux;
            } else {
                if (pathAux.size() != 0) {
                    int start = path.indexOf(pathAux.get(0));
                    path.addAll(start, pathAux);
                    pathEdge.addAll(start, pathEdgeAux);
                    pathAux = new ArrayList<Node>();
                    pathEdgeAux = new LinkedList<Edge>();
                    x=0;
                } else
                    x++;
                if (x>=path.size()) {
                    break;
                } current = path.get(x);
            }
        }
        return pathEdge;
    }

    /**
     * Calcula o custo total do caminho a ser percorrido pelos Carteiros, ou seja, do Grafo.
     * @return um inteiro representando o custo.
     */

    public int getTotalCost () {
        LinkedList<Edge> aux = new LinkedList<Edge>();
        int result = 0;
        int i = 0;
        aux = this.eulerianPath();
        while (i < aux.size()) {
            result = result + aux.get(i).getWeight();
            i++;
        }
        return result;
    }

    /**
     * Função que testa se alguma distancia é maior que o carteiro pode percorrer.
     * @param maxDistance - Distancia maxima que um carteiro pode percorrer.
     * @return True - Não há tal distancia ou False, caso haja.
     */

    public boolean checkMax (int maxDistance) {
        for(List<Edge> l : getMatrix()){
            for(Edge e : l){
                if (e.getWeight() > maxDistance) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * Função responsável por dividir a rota de cada carteiro.
     * @param maxDistance - Distância máxima que cada carteiro pode percorrer.
     * @return Uma arvore AVL que contem os Carteiros e suas rotas.
     */

    public AVLTree<Integer, Carteiro> divideCarteiros (int maxDistance) {
        AVLTree<Integer, Carteiro> tree = new AVLTree<Integer, Carteiro>();
        Carteiro postman = new Carteiro();
        LinkedList<Edge> aux = new LinkedList<Edge>();
        LinkedList<Edge> result = new LinkedList<Edge>();
        int maxDist = 0;
        int i = 0;
        boolean flag = false;
        aux = this.eulerianPath();
        postman.setId(i);
        while (aux.size() != 0) {
            System.out.println(aux.size() + " " + maxDist + " " + aux.get(0).getWeight());
            if (maxDist + aux.get(0).getWeight() <= maxDistance) {
                maxDist = maxDist + aux.get(0).getWeight();
                result.add(aux.remove());
                if (aux.size() == 0)
                    flag = true;
            }
            else {
                postman.setEdges(result);
                try {
                    tree.insert(i, postman);
                } catch (ElementAlreadyExistsException e) {
                    return null;
                }
                i++;
                maxDist = 0;
                result = new LinkedList<Edge>();
                postman = new Carteiro();
                postman.setId(i);
            }
        }
        if (flag) {
            postman.setEdges(result);
            try {
                tree.insert(i, postman);
            } catch (ElementAlreadyExistsException e) {
                return null;
            }
        }
        return tree;
    }

    /**
     * Retorna os sucessores de um dado vértice.
     * @param id - O id do vértice.
     * @return Lista de nós sucessores do vértice.
     */

    public LinkedList<Node> getSucessors(int id) {
        Iterator<Edge> it;
	it = getEdgesList(id).iterator();
        LinkedList<Node> nodeList = new LinkedList<Node>();
        while (it.hasNext()) {
            nodeList.add(it.next().getMate(id));
        }
        return nodeList;
    }

    /**
     * Imprime os vertices de uma dada lista.
     * @param a - A lista de vértices a serem imprimidos.
     */

    public void printNodes (List<Node> a) {
        int i = 0;
        while (i < a.size()) {
            System.out.println(a.get(i).getId());
            i++;
        }
    }

    /**
     * Imprime as arestas de uma dada Lista de Adjacencia.
     * @param b - A lista de Adjacência a ser imprimida.
     */
    public void printEdges (List<List<Edge>> b) {
        for(List<Edge> l : b){
            System.out.println("Vertice " + l.get(0).getId() + " liga com: \n");
            for(Edge e : l){
                System.out.println(e.getIde());
            }
        }
    }

    /**
     * Imprimi uma dada lista de arestas.
     * @param b - Lista de Arestas
     */

    public void printEdgesList (List<Edge> b) {
        for (Edge e : b) {
            System.out.println(e.getId() + " " + e.getIde());
        }
    }

}
